package com.example.springboottest.example.sort;

/**
 * 快速排序，时间复杂度O(n)，  冒泡排序的升级版  也是递归查询   也是不稳定排序
 * 快速排序是由冒泡排序改进而得到的，是一种分区交换排序方法。思想如下：
 * 一趟快速排序采用从两头向中间扫描的方法，同时交换与基准记录逆序的记录。
 * <p>
 * 选定一个基准值，可以是头也可以是尾，本例是头
 * 增大了记录的比较和移动距离，从而减少了总的移动次数
 */
public class QuickSort extends SortBase {
    public static void main(String[] args) {
        QuickSort sort = new QuickSort();
        sort.sort(sort.dataArr);
//        sort.show(sort.dataArr);
    }

    @Override
    public void sort(int[] dataArr) {
        quickSort(dataArr, 0, dataArr.length - 1);
    }

    /**
     * @param arr        待排序列
     * @param leftIndex  待排序列起始位置
     * @param rightIndex 待排序列结束位置
     */
    private void quickSort(int[] arr, int leftIndex, int rightIndex) {
        show(arr);

        if (leftIndex >= rightIndex) {
            return;
        }

        int left = leftIndex;
        int right = rightIndex;
        //待排序的第一个元素作为基准值
        int key = arr[left];
        System.out.println("基准值是\t" + key);
        //从左右两边交替扫描，直到left = right
        while (left < right) {
            while (right > left && arr[right] >= key) {
                //从右往左扫描，找到第一个比基准值小的元素
                right--;
            }

            //找到这种元素将arr[right]放入arr[left]中
            arr[left] = arr[right];

            while (left < right && arr[left] <= key) {
                //从左往右扫描，找到第一个比基准值大的元素
                left++;
            }

            //找到这种元素将arr[left]放入arr[right]中
            arr[right] = arr[left];
        }
        //基准值归位
        arr[left] = key;
        //对基准值左边的元素进行递归排序
        quickSort(arr, leftIndex, left - 1);
        //对基准值右边的元素进行递归排序。
        quickSort(arr, right + 1, rightIndex);
    }
}
